This invention relates generally to analysis of program code and, more specifically, relates to static analysis of program code.
This section is intended to provide a background or context to the invention disclosed below. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived, implemented or described. Therefore, unless otherwise explicitly indicated herein, what is described in this section is not prior art to the description in this application and is not admitted to be prior art by inclusion in this section.
Static security analysis is a specific form of data flow analysis that analyzes program code without execution of the program code. Instead, model(s) are made of the program code and those models are analyzed. For instance, an input program may be modeled as an interprocedural control-flow graph with certain privileged nodes:                Source nodes are statements reading (untrusted) user-provided data;        Sink nodes are statements performing security-sensitive operations; and        Finally, downgrader nodes are statements endorsing the user-provided input (e.g., turning untrusted data to trusted data) either by sanitizing the input or by validating the input. Untrusted data is typically referred to as being potentially tainted (e.g., as in an operating program, the data may not actually be tainted but is assumed to be potentially tainted for analysis).        
An exemplary goal of static security analysis is to find data-flow paths extending from sources to sinks that do not go through downgraders. The implication is that untrusted data is able to reach a security-sensitive operation without first being endorsed.
The only practical way of carrying out static security analysis is by applying a functional approach to interprocedural analysis. See M. Sharir and Amir Pnueli, “Two Approaches to Interprocedural Data Flow Analysis”, Technical Report, New York University, 1978. Specific polynomial algorithms—like the IFDS (Interprocedural, Finite, Distribution, Subset) framework—are used by commercial solutions for security analysis. An IFDS framework is described in T. Reps, S. Horwitz, and M. Sagiv, “Precise Interprocedural Dataflow Analysis via Graph Reachability”, POPL 1995.
The main idea of functional—or summary-based—interprocedural analysis is to create a reusable input-output summary for the target method for the specific data flow fact flowing into the method. That is, the summary may be reused each time the target method is called. This form of memorization is useful and effective in one of the two following cases:
1. The domain of data flow facts is small.
2. The domain is potentially large, but the method behaviors demonstrated during analysis are constrained.
Unfortunately, static security analysis has neither of these properties in general. The domain is exponential in the program size, and the method behaviors examined by the analysis are in some cases are very wide and varied.